#include <stdio.h>
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end =i;
        int tmp = a[end + 1];
		while (end >= 0)
		{

			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;







			}
			else
			{
				break;
			}









		}
		a[end + 1] = tmp;
	}








}
void ShellSort(int* a, int n)
{
	int gap = 3;
	while (gap >= 1)
	{
		gap /= 2;
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;







					}
					else
					{
						break;
					}








				}
				a[end + gap] = tmp;
			}
		}





	}
	







}
void swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;







}
void SelectSort(int* a, int n)
{
	int maxi = 0;
	int mini = 0;
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		maxi = begin;
		mini = begin;
		for (int i = begin+1; i <=end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;

			}







		}
		swap(&a[begin], &a[mini]);
		swap(&a[end], &a[maxi]);
		begin++;
		end--;












	}

















}
int main()
{
	int arr[] = {10,5,2,1,6,3,9,8,7,4 };
	//InsertSort(arr,10);
	//hellSort(arr,10);
     SelectSort(arr,10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}








}